package com.umgsai.wx.backend.test;

public class ExistString {

    /**
     * https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/58wowd/
     * @param args
     */
    public static void main(String[] args) {
        char[][] array = new char[][]{{'A', 'B', 'C', 'E' }, {'S', 'F', 'C', 'S' }, {'A', 'D', 'E', 'E' }};
        boolean exist = exist(array, "ABCCED");
        System.out.println(exist);
    }

    public static boolean exist(char[][] board, String word) {
        boolean res = false;
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++) {
                res = res || dfs(board, word, i, j, 0);
            }
        return res;

    }

    public static boolean dfs(char[][] board, String word, int i, int j, int wordIndex) {
        // 递归终止返回
        if (wordIndex >= word.length()) {
            return true;
        }
        // 边界剪枝
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return false;
        }
        // 不可访问剪枝
        if (board[i][j] == '\0') {
            return false;
        }
        // 不匹配剪枝
        if (board[i][j] != word.charAt(wordIndex)) {
            return false;
        }
        // 对当前位置的上下左右进行下一步dfs
        boolean result = false;
        board[i][j] = '\0'; // 下一步dfs之前，将当前位置标记为不可访问
        result = result || dfs(board, word, i - 1, j, wordIndex + 1);
        result = result || dfs(board, word, i + 1, j, wordIndex + 1);
        result = result || dfs(board, word, i, j - 1, wordIndex + 1);
        result = result || dfs(board, word, i, j + 1, wordIndex + 1);
        board[i][j] = word.charAt(wordIndex); // 在下一步dfs之后，将当前位置的信息恢复。
        // 返回递归结果
        return result;
    }
}
